package acm.pacific2007.northwest;

import java.util.Scanner;


public class p3064 {

	static long nTest;
	static String code, numStr;
	static long num, converted;

	public static void main(String[] args) throws Exception {

		Scanner scanner = new Scanner(System.in);
//		Scanner scanner = new Scanner(new File("test.in"));
		
		nTest = scanner.nextLong();
		for (long i=1;i<=nTest;++i) {
			code = scanner.next();
			numStr = scanner.next();
			num = Long.parseLong(numStr);
			if (code.charAt(0)=='b') {
				System.out.print("From binary: " + numStr + " is ");
				converted = 0;
				long tmp = 1;
				while (num > 0) {
					long re = num % 10;
					num /= 10;
					converted += re * tmp;
					tmp *= -2;
				}
				System.out.println(converted);
			}
			else {
				System.out.print("From decimal: " + numStr + " is ");
				converted = 0;
				long tmp = 1;
				while (num != 0) {
					if (num%-2 !=0) {
						num--;
						converted += 1 * tmp;
					}
					num /= -2;
					tmp *= 10;
				}
				System.out.println(converted);
			}
		}

	}

}
